/**
 * 
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
 * 左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。
 * 0 <= s.length <= 3 * 104
 * s[i] 为 '(' 或 ')'
 */


 class Solution {
public:
    //method1
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n);
        int maxLen = 0;

        for(int i = 1,pre = 0;i < n;i++){
            if(s[i] == ')'){
                pre = i - dp[i - 1] - 1;
                if(pre >= 0 and s[pre] == '('){
                    dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
                    maxLen = max(maxLen,dp[i]);
                }
            }
        }
        return maxLen;
    }

    //method 2
    int longestValidParentheses(string s) {
        int ans = 0;
        stack<int>stk;
        stk.push(-1);
        for(int i = 0;i < s.size();i++){
            if(s[i] == '('){
                stk.push(i);
            }else{
                stk.pop();
                if(stk.empty()){
                    stk.push(i);
                }else{
                    ans = max(ans,i - stk.top());
                }
            }
        }
        return ans;
    }
};